﻿namespace Graph;

public class DFSBipartitionDetection
{
    private IGraph G;
    private bool[] visited;
    private bool[] colors; //红为false，绿为true，初始染色为红。

    public bool IsBipartite { get; private set; } = true; //假定图是二分图

    public DFSBipartitionDetection(IGraph G)
    {
        this.G = G;

        visited = new bool[G.V];
        colors = new bool[G.V];

        for (int v = 0; v < G.V; v++) 
        {
            if (!visited[v])
            {
                DFS(v); //检查图的所有连通分量都是二分图？
            }
        }
    }
    
    private void DFS(int v)
    {
        visited[v] = true;

        foreach (int w in G.Adj(v))
        {
            if (!visited[w])
            {
                colors[w] = !colors[v]; //染为相反色
                DFS(w);
            }
            else if (colors[w] == colors[v]) //违反二分图性质
            {
                IsBipartite = false; //只要有一个连通分量不是二分图，那就判定它不是二分图。
                break;
            }
        }
    }

    //验证
    static void Main(string[] args)
    {
        IGraph graph = new AdjLinkList("图的二分检测/g2.txt");
        DFSBipartitionDetection bipartitionDetection = new(graph);
        Console.WriteLine(bipartitionDetection.IsBipartite);

        Console.Read();
    }
}
